namespace ds
{
    // 红黑树节点可能的颜色。
    const RED_BLACK_TREE_COLORS = {
        red: 'red',
        black: 'black',
    };

    // 节点元信息中的颜色属性名。
    const COLOR_PROP_NAME = 'color';

    /**
     * 红黑树
     * 
     * 红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组
     * 
     * @see https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/tree/red-black-tree/RedBlackTree.js
     * @see https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
     */
    export class RedBlackTree<T> extends BinarySearchTree<T>
    {
        /**
         * 插入值
         * 
         * @param value 值
         */
        insert(value: T)
        {
            const insertedNode = super.insert(value);

            // 判断是否为根结点
            if (this.nodeComparator.equal(insertedNode, this.root))
            {
                // 使根永远是黑色的。
                this.makeNodeBlack(insertedNode);
            } else
            {
                // 将所有新插入的节点设置为红色。
                this.makeNodeRed(insertedNode);
            }

            // 检查所有条件并平衡节点。
            this.balance(insertedNode);

            return insertedNode;
        }

        /**
         * 移除指定值 （禁止使用）
         * 
         * @param value 值
         */
        remove(value: T)
        {
            throw new Error(`不能删除 ${ value }。移除方法尚未实现`);
            return true;
        }

        /**
         * 从指定结点平衡树
         * 
         * @param node 结点
         */
        balance(node: BinarySearchTreeNode<T>)
        {
            // 如果它是根节点，那么这里就没有什么需要平衡的了。
            if (this.nodeComparator.equal(node, this.root))
            {
                return;
            }

            // 如果父结点是黑色的，则完成。这里没有什么需要平衡的。
            if (this.isNodeBlack(node.parent))
            {
                return;
            }

            const grandParent = node.parent.parent;

            if (node.uncle && this.isNodeRed(node.uncle))
            {
                // 如果node有red 叔伯，那么我们需要重新上色。

                // 重新上色父结点和叔伯结点到黑色。
                this.makeNodeBlack(node.uncle);
                this.makeNodeBlack(node.parent);

                if (!this.nodeComparator.equal(grandParent, this.root))
                {
                    // 如果不是根结点，则将祖父结点重新上色为红色。
                    this.makeNodeRed(grandParent);
                } else
                {
                    //如果祖父结点是黑根结点，什么都不要做。
                    //因为root已经有了两个我们刚刚重新上色的黑色同胞。
                    return;
                }

                // 现在进一步检查重新着色的祖父母。
                this.balance(grandParent);
            } else if (!node.uncle || this.isNodeBlack(node.uncle))
            {
                // 如果叔伯结点是黑色或者不存在，那么我们需要执行旋转。
                if (grandParent)
                {
                    // 旋转后的得到的新祖父结点
                    let newGrandParent: BinarySearchTreeNode<T>;

                    if (this.nodeComparator.equal(grandParent.left, node.parent))
                    {
                        // Left case.
                        if (this.nodeComparator.equal(node.parent.left, node))
                        {
                            // Left-left case.
                            newGrandParent = this.leftLeftRotation(grandParent);
                        } else
                        {
                            // Left-right case.
                            newGrandParent = this.leftRightRotation(grandParent);
                        }
                    } else
                    {
                        // Right case.
                        if (this.nodeComparator.equal(node.parent.right, node))
                        {
                            // Right-right case.
                            newGrandParent = this.rightRightRotation(grandParent);
                        } else
                        {
                            // Right-left case.
                            newGrandParent = this.rightLeftRotation(grandParent);
                        }
                    }

                    // 如果没有父结点，则将newGrandParent设为根结点。
                    if (newGrandParent && newGrandParent.parent === null)
                    {
                        this.root = newGrandParent;

                        // 把根结点重新上色为黑色
                        this.makeNodeBlack(this.root);
                    }

                    // 检查新祖父母是否没有违反红黑树规则。
                    this.balance(newGrandParent);
                }
            }
        }

        /**
         * Left Left Case (p is left child of g and x is left child of p)
         * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
         * @return {BinarySearchTreeNode}
         */
        leftLeftRotation(grandParentNode: BinarySearchTreeNode<T>)
        {
            // Memorize the parent of grand-parent node.
            const grandGrandParent = grandParentNode.parent;

            // Check what type of sibling is our grandParentNode is (left or right).
            let grandParentNodeIsLeft;
            if (grandGrandParent)
            {
                grandParentNodeIsLeft = this.nodeComparator.equal(grandGrandParent.left, grandParentNode);
            }

            // Memorize grandParentNode's left node.
            const parentNode = grandParentNode.left;

            // Memorize parent's right node since we're going to transfer it to
            // grand parent's left subtree.
            const parentRightNode = parentNode.right;

            // Make grandParentNode to be right child of parentNode.
            parentNode.setRight(grandParentNode);

            // Move child's right subtree to grandParentNode's left subtree.
            grandParentNode.setLeft(parentRightNode);

            // Put parentNode node in place of grandParentNode.
            if (grandGrandParent)
            {
                if (grandParentNodeIsLeft)
                {
                    grandGrandParent.setLeft(parentNode);
                } else
                {
                    grandGrandParent.setRight(parentNode);
                }
            } else
            {
                // Make parent node a root
                parentNode.parent = null;
            }

            // Swap colors of granParent and parent nodes.
            this.swapNodeColors(parentNode, grandParentNode);

            // Return new root node.
            return parentNode;
        }

        /**
         * Left Right Case (p is left child of g and x is right child of p)
         * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
         * @return {BinarySearchTreeNode}
         */
        leftRightRotation(grandParentNode: BinarySearchTreeNode<T>)
        {
            // Memorize left and left-right nodes.
            const parentNode = grandParentNode.left;
            const childNode = parentNode.right;

            // We need to memorize child left node to prevent losing
            // left child subtree. Later it will be re-assigned to
            // parent's right sub-tree.
            const childLeftNode = childNode.left;

            // Make parentNode to be a left child of childNode node.
            childNode.setLeft(parentNode);

            // Move child's left subtree to parent's right subtree.
            parentNode.setRight(childLeftNode);

            // Put left-right node in place of left node.
            grandParentNode.setLeft(childNode);

            // Now we're ready to do left-left rotation.
            return this.leftLeftRotation(grandParentNode);
        }

        /**
         * Right Right Case (p is right child of g and x is right child of p)
         * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
         * @return {BinarySearchTreeNode}
         */
        rightRightRotation(grandParentNode: BinarySearchTreeNode<T>)
        {
            // Memorize the parent of grand-parent node.
            const grandGrandParent = grandParentNode.parent;

            // Check what type of sibling is our grandParentNode is (left or right).
            let grandParentNodeIsLeft;
            if (grandGrandParent)
            {
                grandParentNodeIsLeft = this.nodeComparator.equal(grandGrandParent.left, grandParentNode);
            }

            // Memorize grandParentNode's right node.
            const parentNode = grandParentNode.right;

            // Memorize parent's left node since we're going to transfer it to
            // grand parent's right subtree.
            const parentLeftNode = parentNode.left;

            // Make grandParentNode to be left child of parentNode.
            parentNode.setLeft(grandParentNode);

            // Transfer all left nodes from parent to right sub-tree of grandparent.
            grandParentNode.setRight(parentLeftNode);

            // Put parentNode node in place of grandParentNode.
            if (grandGrandParent)
            {
                if (grandParentNodeIsLeft)
                {
                    grandGrandParent.setLeft(parentNode);
                } else
                {
                    grandGrandParent.setRight(parentNode);
                }
            } else
            {
                // Make parent node a root.
                parentNode.parent = null;
            }

            // Swap colors of granParent and parent nodes.
            this.swapNodeColors(parentNode, grandParentNode);

            // Return new root node.
            return parentNode;
        }

        /**
         * Right Left Case (p is right child of g and x is left child of p)
         * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
         * @return {BinarySearchTreeNode}
         */
        rightLeftRotation(grandParentNode: BinarySearchTreeNode<T>)
        {
            // Memorize right and right-left nodes.
            const parentNode = grandParentNode.right;
            const childNode = parentNode.left;

            // We need to memorize child right node to prevent losing
            // right child subtree. Later it will be re-assigned to
            // parent's left sub-tree.
            const childRightNode = childNode.right;

            // Make parentNode to be a right child of childNode.
            childNode.setRight(parentNode);

            // Move child's right subtree to parent's left subtree.
            parentNode.setLeft(childRightNode);

            // Put childNode node in place of parentNode.
            grandParentNode.setRight(childNode);

            // Now we're ready to do right-right rotation.
            return this.rightRightRotation(grandParentNode);
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} node
         * @return {BinarySearchTreeNode}
         */
        makeNodeRed(node: BinarySearchTreeNode<T>)
        {
            node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.red);

            return node;
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} node
         * @return {BinarySearchTreeNode}
         */
        makeNodeBlack(node: BinarySearchTreeNode<T>)
        {
            node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.black);

            return node;
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} node
         * @return {boolean}
         */
        isNodeRed(node: BinarySearchTreeNode<T>)
        {
            return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.red;
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} node
         * @return {boolean}
         */
        isNodeBlack(node: BinarySearchTreeNode<T>)
        {
            return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.black;
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} node
         * @return {boolean}
         */
        isNodeColored(node: BinarySearchTreeNode<T>)
        {
            return this.isNodeRed(node) || this.isNodeBlack(node);
        }

        /**
         * @param {BinarySearchTreeNode|BinaryTreeNode} firstNode
         * @param {BinarySearchTreeNode|BinaryTreeNode} secondNode
         */
        swapNodeColors(firstNode: BinarySearchTreeNode<T>, secondNode: BinarySearchTreeNode<T>)
        {
            const firstColor = firstNode.meta.get(COLOR_PROP_NAME);
            const secondColor = secondNode.meta.get(COLOR_PROP_NAME);

            firstNode.meta.set(COLOR_PROP_NAME, secondColor);
            secondNode.meta.set(COLOR_PROP_NAME, firstColor);
        }
    }

}